# coding: utf-8

from typing import Optional, Sequence, Any, Tuple
from io import StringIO
from .Graph import Graph, vertex_t, edge_t, INVALID_EDGE, INVALID_VERTEX

"""
Subgraph of a given graph - subset of its vertices + all edges between those vertices.

Vertices which are added after the construction are called dummy vertices.
They are equal to the original vertices (there can be eges added or removed between them), but their size is always zero.
They can be used to distinguis between the vertices of the original graph and vertices which were added for "algorithmic" purpouses.
"""


class Subgraph:
    g: Graph
    m_vertices: Sequence[vertex_t]
    m_dummy_border: vertex_t

    # 用户可以自定义要传入的节点集合
    def __init__(self, g: Graph, vertices: Sequence[vertex_t] = []):
        self.g = g

        if len(vertices) != 0:
            self.m_vertices = vertices
            self.m_dummy_border = 1 + max(vertices)
        else:
            self.m_vertices = g.get_all_nodes()
            self.m_dummy_border = g.node_count()

    # TODO: 当前未处理多源多汇, 可能存在多个源点汇点
    def get_source(self):
        source = INVALID_VERTEX
        for v in self.g.get_all_nodes():
            if self.indeg[v] == 0:
                source = v
                break
        return source
    
    def get_target(self):
        target = INVALID_VERTEX
        for v in self.g.get_all_nodes():
            if self.outdeg[v] == 0:
                target = v
                break
        return target

    def get_node_attr(self, u: vertex_t, name: str):
        return self.g.get_node_attr(u, name)

    def get_edge_attr(self, e: edge_t, name: str):
        return self.g.get_edge_attr(e, name)

    def get_uv_edge_attr(self, u: vertex_t, v: vertex_t, name: str, directed=True):
        return self.g.get_uv_edge_attr(u, v, name, directed)

    def get_edge(self, u: vertex_t, v: vertex_t, directed=True) -> edge_t:
        e = self.g.get_edge(u, v, directed=directed)
        return e if e >= 0 else INVALID_EDGE

    def get_edge_uv_tuple(self, e: edge_t) -> Optional[Tuple[vertex_t, vertex_t]]:
        return self.g.get_edge_uv_tuple(e)

    def set_node_attr(self, u: vertex_t, name: str, value: Any):
        self.g.set_node_attr(u, name, value)

    def set_node_array_attr(self, u: vertex_t, name: str, i: int, value: Any):
        attr = self.g.get_node_attr(u, name)
        if type(attr) == list and i > -1 and i < len(attr):
            attr[i] = value
            self.g.set_node_attr(u, name, attr)

    def get_node_array_attr(self, u: vertex_t, name: str, i: int):
        attr = self.g.get_node_attr(u, name)
        if type(attr) == list and i > -1 and i < len(attr):
            return attr[i]
        return None

    def set_edge_attr(self, e: edge_t, name: str, value: Any):
        self.g.set_edge_attr(e, name, value)

    def set_uv_edge_attr(self, u: vertex_t, v: vertex_t, name: str, value: Any):
        self.g.set_uv_edge_attr(u, v, name, value)

    def set_all_nodes_attr(self, name: str, value: Any, update_mode=False):
        self.g.set_all_nodes_attr(name, value, update_mode)

    def set_all_edges_attr(self, name: str, value: Any, update_mode=False):
        self.g.set_all_edges_attr(name, value, update_mode)

    def remove_all_nodes_attr(self, name: str):
        self.g.remove_all_nodes_attr(name)

    def remove_all_edges_attr(self, name: str):
        self.g.remove_all_edges_attr(name)

    def node_count(self):
        return len(self.m_vertices)

    def edge_count(self):
        return self.g.edge_count()

    def add_edge(self, u: vertex_t, v: vertex_t):
        self.g.add_edge(u, v)

    def add_dummy_node(self) -> vertex_t:
        u = self.g.add_node()
        self.m_vertices.append(u)
        return u

    def is_dummy_node(self, u: vertex_t):
        return u >= self.m_dummy_border

    def remove_edge(self, u: vertex_t, v: vertex_t):
        self.g.remove_edge(u, v)

    def has_edge(self, u: vertex_t, v: vertex_t):
        return v in self.out_neighbours(u)

    def has_node(self, u: vertex_t):
        return self.g.has_node(u)

    def out_neighbours(self, u: vertex_t) -> Sequence[vertex_t]:
        return self.g.out_neighbours(u)

    def in_neighbours(self, u: vertex_t) -> Sequence[vertex_t]:
        return self.g.in_neighbours(u)

    def neighbours(self, u: vertex_t) -> Sequence[vertex_t]:
        nodes = self.out_neighbours(u)
        nodes.extend(self.in_neighbours(u))
        return nodes

    def out_neighbour(self, u: vertex_t, i: int) -> vertex_t:
        return self.g.out_neighbour(u, i)

    def in_neighbour(self, u: vertex_t, i: int) -> vertex_t:
        return self.g.in_neighbour(u, i)

    def out_degree(self, u: vertex_t) -> int:
        return self.g.out_degree(u)

    def in_degree(self, u: vertex_t) -> int:
        return self.g.in_degree(u)

    def get_all_nodes(self):
        return self.m_vertices

    def get_all_edges(self):
        return self.g.get_all_edges()

    def get_node(self, i: int):
        return self.m_vertices[i]

    def delete_nodes(self, nodes):
        self.g.delete_nodes(nodes)

    def __str__(self):
        out = StringIO()
        for u in self.g.get_all_nodes():
            out.write("%d: {" % u)
            sep = ""
            for v in self.g.out_neighbours(u):
                out.write(f"{sep}{v}")
                sep = ", "
            out.write("\n")
        return out.getvalue()


# Recursively assign u and all vertices reachable from u in the underlying undirected graph to the same component.


def split_component(g: Graph, component: Sequence[vertex_t], u: vertex_t):
    g.set_node_attr(u, "done", True)
    component.append(u)
    for v in g.out_neighbours(u):
        if not g.get_node_attr(v, "done"):
            split_component(g, component, v)

    for v in g.in_neighbours(u):
        if not g.get_node_attr(v, "done"):
            split_component(g, component, v)


# Split the given graph into connected components represented by subgrapgs.
def split_graph(g: Graph) -> Sequence[Subgraph]:
    components: Sequence[Sequence[vertex_t]] = []
    g.set_all_nodes_attr("done", False)

    for u in g.get_all_nodes():
        if not g.get_node_attr(u, "done"):
            components.append([])
            split_component(g, components[-1], u)

    subgraphs: Sequence[Subgraph] = []
    for component in components:
        subgraphs.append(Subgraph(g, component))
    return subgraphs
